package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/16 9:04
 * https://leetcode-cn.com/problems/evaluate-division/
 */
public class Title399 {

    public static double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        //<k,<k,v>>
        Map<String, Map<String, Double>> graph = new HashMap<>();
        //初始化图
        for (int i = 0; i < equations.size(); i++) {
            List<String> edge = equations.get(i);
            graph.computeIfAbsent(edge.get(0), k -> new HashMap<>()).put(edge.get(1), values[i]);
            graph.computeIfAbsent(edge.get(1), k -> new HashMap<>()).put(edge.get(0), 1 / values[i]);
        }
        double[] result = new double[queries.size()];
        int count = 0;
        for (List<String> temp: queries) {
            String a = temp.get(0);
            if (!graph.containsKey(a)) {
                result[count++] = -1.0;
                continue;
            }
            String b = temp.get(1);
            if (!graph.containsKey(b)) {
                result[count++] = -1.0;
                continue;
            }
            //标志节点判断是否访问过
            Set<String> flag = new HashSet<>();
            result[count++] = dfs(graph, flag, a, b, 1.0);
        }
        return result;
    }

    private static double dfs(Map<String, Map<String, Double>> graph, Set<String> flag, String a, String b, double temp) {
        if (flag.contains(a)) {
            return -1.0;
        }
        if (a.equals(b)) {
            return temp;
        }
        //标志集合中添加a，防止绕圈
        flag.add(a);
        Map<String, Double> stringDoubleMap = graph.get(a);
        Set<String> nodes = stringDoubleMap.keySet();
        for (String node: nodes) {
            double query = dfs(graph,flag,node,b,temp * stringDoubleMap.get(node));
            if (query != -1.0) {
                return query;
            }
        }
        return -1.0;
    }

    public static void main(String[] args) {
        List<List<String>> equation = new ArrayList<>();
        List<String> temp = new ArrayList<>();
        temp.add("a");
        temp.add("b");
        equation.add(new ArrayList<>(temp));
        temp.clear();
        temp.add("b");
        temp.add("c");
        equation.add(temp);
        double[] value = {2.0, 3.0};
        List<List<String>> querys = new ArrayList<>();
        List<String> e = new ArrayList<>();
        e.add("a");
        e.add("c");
        querys.add(new ArrayList<>(e));
        e.clear();
        e.add("b");
        e.add("a");
        querys.add(e);
        calcEquation(equation,value,querys);
    }
}
